package com.company.graph;

public class 岛屿数量 {


    final static int[][] Ds = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;

        final int row = grid.length;
        final int col = grid[0].length;

        boolean[][] visited = new boolean[row][col];
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(grid,i,j,visited);
                    res++;
                }
            }
        }
        return res;
    }

    public void dfs(char[][] grid,int x,int y,boolean[][] visited){
        visited[x][y] = true;
        final int row = grid.length;
        final int col = grid[0].length;
        for (int[] d : Ds) {
            int newRow = x + d[0];
            int newCol = y + d[1];
            if (newRow < row && newRow >= 0 && newCol < col && newCol >= 0 && grid[newRow][newCol] == '1' && !visited[newRow][newCol]) {
                dfs(grid,newRow,newCol,visited);
            }
        }

    }


}
